package algorithms.sorts;

import algorithms.Utils;

import java.util.Arrays;


/**
 * 已完成
 */
public class HeapSort {
    public static void main(String[] args) {

        System.out.print("请输入数组长度:");
        int[] arr = Utils.randomArray(Integer.parseInt(Utils.sysInLine()));
        //int[] arr = {-1159872480, -918151260, -645322593, -251634839, 168166537, 601964429, 793778655, 1991589181, 1064512499, 1188524735};
        //int[] arr = {6, 7, 16, 17, 25, 48, 57, 51, 53, 66, 75, 97};
        System.out.println(Utils.isAscend(arr));
        long start = System.currentTimeMillis();
        System.out.println("heapSort start:" + System.currentTimeMillis());
        heapSort(arr);
        long end = System.currentTimeMillis();
        System.out.println("  heapSort end:" + end);
        System.out.println("  heapSort use:" + (end - start));
        System.out.println(Utils.isAscend(arr));
        if (arr.length <= 100) {
            System.out.println(Arrays.toString(arr));
        }
    }

    public static void heapSort(int[] arr) {
        //childrenInsertBuildMaxHeap(arr);
        //insertBuildMaxHeap(arr);
        //top2DownBuildMaxheap(arr);
        down2TopBuildMaxHeap(arr);
        int i = arr.length - 1;
        while (i > 0) {
            Utils.swap(arr, 0, i--);
            heapify(arr, i);
        }
    }

    //---------------------插入法构造------------------------

    /**
     * 孩子插入法(逻辑复杂)
     *
     * @param arr
     */
    private static void childrenInsertBuildMaxHeap(int[] arr) {
        for (int i = 0; i <= arr.length / 2 - 1; i++) {
            int l = 2 * i + 1;
            int r = 2 * i + 2;
            int min = -1;//表示没有右孩子
            int max = l;
            if (r < arr.length) {
                max = arr[l] > arr[r] ? l : r;
                min = arr[l] > arr[r] ? r : l;
            }

            if (arr[i] < arr[max]) {
                Utils.swap(arr, i, max);
            }
            insertAndAdjust(arr, i);
            if (min > -1) {
                insertAndAdjust(arr, min);
            }
        }
    }


    /**
     * 当前节点插入法构造堆(简单)
     */
    private static void insertBuildMaxHeap(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            insertAndAdjust(arr, i);
        }
    }

    private static void insertAndAdjust(int[] arr, int i) {
        while (i > 0) {
            int p = (i + 1) / 2 - 1;
            if (arr[p] < arr[i]) {
                Utils.swap(arr, p, i);
            }
            i = p;
        }
    }
    //---------------------插入法构造------------------------


    //---------------------自顶而下构造----------------
    private static void top2DownBuildMaxheap(int[] arr) {
        recursiveBuildMaxheap(arr, 0);
    }

    //递归，可转换为迭代
    private static void recursiveBuildMaxheap(int[] arr, int top) {

        int l = top * 2 + 1;
        int r = top * 2 + 2;
        boolean nonLeaf = false;
        if (l <= arr.length - 1) {
            nonLeaf = true;
            recursiveBuildMaxheap(arr, l);
        }
        if (r <= arr.length - 1) {
            nonLeaf = true;
            recursiveBuildMaxheap(arr, r);
        }
        //左右树构造大顶堆之后，将当前节点加入，进行堆规范化
        if (nonLeaf) heapify(top, arr);

    }
    //---------------------自顶而下构造----------------

    //---------------------自底向上构造-------------------------
    private static void down2TopBuildMaxHeap(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(i, arr);
        }
    }
    //---------------------自底向上构造-------------------------

    private static void heapify(int top, int[] arr, int end) {
        int i = top;
        while (i <= (end + 1) / 2 - 1) {
            int l = 2 * i + 1;
            int r = 2 * i + 2;
            int max = r == end + 1 ? l : (arr[l] > arr[r] ? l : r);
            if (arr[i] < arr[max]) {
                Utils.swap(arr, max, i);
                i = max;
            } else break;
        }
    }

    private static void heapify(int[] arr, int end) {
        heapify(0, arr, end);
    }

    private static void heapify(int top, int[] arr) {
        heapify(top, arr, arr.length - 1);
    }
}
